package com.es.tmp;

import com.es.bst.AbstractBinarySearchTree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author 二十
 * @since 2022/1/19 4:54 下午
 */
public class Bst<E extends Comparable<E>> extends AbstractBinarySearchTree<E> {

    class Node {
        Node left;
        Node right;
        E data;

        public Node() {
        }

        public Node(E data) {
            this.data = data;
        }

        public Node(Node left, Node right, E data) {
            this.left = left;
            this.right = right;
            this.data = data;
        }

        @Override
        public String toString() {
            return this.data + "";
        }
    }

    private Node root;
    private int size;

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public void add(E data) {
        root = add(root, data);
    }

    private Node add(Node node, E data) {
        if (node == null) {
            size++;
            return new Node(data);
        }
        if (data.compareTo(node.data) < 0) {
            //此时应该落在左子树上
            node.left = add(node.left, data);
        } else if (data.compareTo(node.data) > 0) {
            //此时应该落在右子树上
            node.right = add(node.right, data);
        }

        return node;
    }

    @Override
    public boolean contains(E e) {
        return contains(root, e);
    }

    private boolean contains(Node node, E e) {
        if (node == null) {
            return false;
        }
        if (node.data.compareTo(e) == 0) {
            return true;
        }
        if (e.compareTo(node.data) < 0) {
            return contains(node.left, e);
        } else if (e.compareTo(node.data) > 0) {
            return contains(node.right, e);
        }
        return false;
    }

    @Override
    public void preOrder() {
        preOrder(root);
    }

    private void preOrder(Node node) {
        if (node == null) {
            return;
        }
        System.out.println(node);
        preOrder(node.left);
        preOrder(node.right);
    }

    @Override
    public void midOrder() {
        midOrder(root);
    }

    private void midOrder(Node node) {
        if (node == null) {
            return;
        }
        midOrder(node.left);
        System.out.println(node);
        midOrder(node.right);
    }

    @Override
    public void postOrder() {
        postOrder(root);
    }

    private void postOrder(Node node) {
        if (node == null) {
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node);
    }

    @Override
    public void preOrderNR() {
        //栈
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            System.out.println(node);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }

    @Override
    public void guangOrder() {
        //队列
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            System.out.println(node);
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }

    @Override
    public E minElement() {
        if (isEmpty()) {
            return null;
        }

        return minElement(root).data;
    }

    private Node minElement(Node node) {

        if (node.left == null) {
            return node;
        }
        return minElement(node.left);
    }

    @Override
    public E removeMinElement() {
        E e = minElement();
        //接下来就就是删除这个节点的步骤
        //删除这个节点需要将这个节点的右子树接在他的父节点左子树，也就是待删除节点的位置
        root = removeMinElement(root);
        return e;
    }

    private Node removeMinElement(Node node) {
        if (node.left==null){
            Node right = node.right;
            node.right=null;
            size--;
            return right;
        }
        node.left=removeMinElement(node.left);
        return node;
    }

    @Override
    public void remove(E e) {
        if (e==null){
            throw new IllegalArgumentException("error args");
        }
        root = remove(root,e);
    }

    private Node remove(Node node, E e) {
        if (node==null){
            return null;
        }
        if (node.data.compareTo(e)>0){
            node.left=remove(node.left,e);
            return node;
        }else if (node.data.compareTo(e)<0){
            node.right= remove(node.right,e);
            return node;
        }else {
            //这个时候就说明，当前节点就是要删除的节点
            if (node.left==null){
                Node right = node.right;
                node.right=null;
                size--;
                return right;
            }
            if (node.right==null){
                Node left = node.left;
                node.left=null;
                size--;
                return left;
            }

            /*
                左右节点都不为空就会走到这里,这个时候需要重新在选出来一个节点替代当前节点[在右子树选出最小节点即可]
                1.拿到待删除节点A的左右子树
                2.找出右子树的最小元素B
                3.从右子树中删除元素B并返回新的右子树节点
                4.让B的右子树指向 ③ 返回的结果
                5.让B的左子树指向A的左子树引用
                6.将待删除节点左右子树置空
             */
            Node right = node.right;

            Node newNode = minElement(right);
            newNode.right = removeMinElement(right);
            newNode.left=node.left;

            node.left=node.right=null;
            return newNode;
        }

    }

    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer("Tree:[\n");
        toString(sb, 0, root);
        return sb.append("]").toString();
    }

    private void toString(StringBuffer sb, int depth, Node node) {
        if (node==null){
            return;
        }
        toString(sb, depth + 1, node.left);
        sb.append(toString(depth) + " " + node.data + "\n");
        toString(sb, depth + 1, node.right);

    }

    private String toString(int depth) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            sb.append("----");
        }
        return sb.toString();
    }
}
